package leetcode_400;

/**
 *@author 周杨
 *CoinChange_322 给定不同面额的硬币 和总额n 求能够兑换的最小硬币数
 *describe:动态规划  count(n,m,coins) = min(count(n,m-1,coins), count(n-coins[m],m,coins))  AC 30%
 *2018年7月3日 下午3:54:56
 */
public class CoinChange_322 {

	public static void main(String[] args) {
		CoinChange_322 test=new CoinChange_322();
		System.out.println(test.coinChange(new int[] {1,2,5},11));
	}
	/**
	 * describe:贪心算法 错误思想 如{1,3,7,8} 14 
	 * 2018年7月3日 下午3:44:25
	 */
	public int coinChange1(int[] coins, int amount) {
        int res=0;
        if(coins.length==0)
        	return -1;
        int index=coins.length-1;
        while(index>=0) {
        	if(amount>=coins[index]) {
        		amount-=coins[index];
        		++res;
        	}
        	else
        		--index;
       }
        if(amount!=0)
        	return -1;
        return res;
    }
	
	/**
	 * describe:动态规划 AC 29%
	 * 2018年7月3日 下午3:54:06
	 */
	public int coinChange(int[] coins, int amount) {
		int[] dp = new int[amount+1];
        for(int i=1; i<=amount; i++) {
            int min = Integer.MAX_VALUE;
            for(int j=0; j<coins.length; j++) {//遍历整个硬币集合
                if(i >= coins[j] && dp[i-coins[j]] != -1)
                    min = Math.min(min,dp[i-coins[j]] + 1);
            }
            dp[i] = (min == Integer.MAX_VALUE) ? -1 : min;
        }
        return dp[amount];
    }
}
